package leetcode.weekly.week330;

import leetcode.helper.H;

//Solution4Test
public class Solution5 {

	int[] array;
	int len;

	public long countQuadruplets(int[] nums) {
		this.array = nums;
		len = nums.length;
		return process(0, len - 1);
	}

	public long process(int L, int R) {
		if (R == L) {
			return 0;
		}
		int M = L + ((R - L) >> 1);
		return process(L, M) + process(M + 1, R) + merge(L, M, R);
	}

	public long merge(int L, int M, int R) {
		long ans = 0;
		int[] help = new int[R - L + 1];
		int p = 0;
		int p10 = L, p20 = M + 1;
		int p1 = L, p2 = M + 1;
		while (p1 <= M && p2 <= R) {
			if (array[p1] < array[p2]) {
				help[p++] = array[p1++];
			} else {
				ans += f(p10, p1 - 1, p2) * f2(p2 + 1, R, p1);
				help[p++] = array[p2++];
			}
		}
		while (p1 <= M) {
			help[p++] = array[p1++];
		}
		while (p2 <= R) {
			help[p++] = array[p2++];
		}
		for (p = 0; p < help.length; p++) {
			array[L + p] = help[p];
		}
		return ans;
	}

	private int f(int l, int r, int target) {
		if (l > r)
			return 0;
		int b = l;
		int ans = l;
		while (l <= r) {
			int m = ((r - l) >> 1) + l;
			if (array[m] < target) {
				ans = m;
				l = m + 1;
			} else {
				r = m - 1;
			}
		}
		return ans - l;
	}

	private int f2(int l, int r, int target) {
		if (l > r)
			return 0;
		int b = r;
		int ans = l;
		while (l <= r) {
			int m = ((r - l) >> 1) + l;
			if (array[m] > target) {
				ans = m;
				r = m - 1;
			} else {
				l = m + 1;
			}
		}
		return b - ans;
	}

	public static void main(String[] args) {
		Solution5 so = new Solution5();
		so.countQuadruplets(H.str2array3("[1,3,2,4,5]"));
	}

}
